Modular arithmetic is a powerful tool in many different disciplines such as cryptography and computer science. With modular arithmetic it is possible to code and decode messages or the like with the aid of microprocessors performing certain steps of multiplication, addition, division and/or subtraction according to certain instructions.
Hereby two integers a and a′ are called congruent modulo n whereas n is a positive integer if a−a′ is an integer multiple of n and it is expressed as a≡a′ (mod n).
If a≡a′ (mod n) and b≡b′ (mod n) then for the integers a, a′, b and b′ the following rules apply:
(a+b)≡(a′+b′) (mod n)
(a−b)≡(a′−b′) (mod n)
(a*b)≡(a′*b′) (mod n).
Especially in security-sensitive computing systems for example in smart card controllers the arithmetic operations performed by a microprocessor may be disturbed or even manipulated by an attack of an unauthorised person called hacker. This can be dangerous since sensitive data might be stolen particularly if cryptography algorithms like RSA are computed by software.
To overcome this problem two well known solutions are common. In a first solution the microprocessor computation hardware is doubled. But this mostly costs too much chip area. In a second solution a double calculation is performed but thereby the system performance is reduced.